11460. K-ый Гутаб

В ADA университете продается n видов гутабов. Гутаб i-го сорта продается за a_i  гяпиков.

Гутаб – азербайджанское блюдо из тонко раскатанного теста, которое быстро готовят на выпуклой сковороде, известной как садж. Вариаций гутаба множество: обычно в качестве начинки используется тыква и зелень. Есть также шамахинский гутаб, яшыл гутаб и карын гутаб, гузу гутаб (ягненок), девэ гутаб, характерные для поселка Джорат. Это региональные вариации гутаба в Азербайджане.

Всего Хусейн купит как минимум один гутаб. Ему разрешено покупать несколько гутабов одного сорта.

Найдите k-ю наименьшую цену, которую может заплатить Хусейн. Если имеется несколько наборов гутабов по одинаковой цене, то цена считается только один раз.

Вход. Первая строка содержит два числа: n (1 ≤ n ≤ 10) и k (1 ≤ k ≤ 2 ⋅ 10⁵).

Вторая строка содержит цены на разные виды гутабов: a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Выход. Выведите k-ую наименьшую цену, которую может заплатить Хусейн.

Пример. Шесть наименьших цен, которые может заплатить Хусейн:

· 5 гяпиков

· 10 гяпиков

· 11 гяпиков

· 15 гяпиков

· 11 + 5 = 16 гяпиков

· 20 гяпиков

Таким образом, ответ 20.

Пример входа	Пример выхода
5 6 5 10 11 15 20	20

РЕШЕНИЕ

структуры данных – set

Анализ алгоритма

Занесем во множество число 0. Затем выполним k шагов:

· Найдём наименьший элемент множества x, и удалим его из множества.

· Для каждого i (1 ≤ i ≤ n) добавим во множество элементы x + a_i;

После выполнения k шагов наименьший элемент множества будет равен k-й наименьшей цене, которую может заплатить Хусейн.

Реализация алгоритма

Читаем входные данные.

scanf("%d %d", &n, &k);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

Заносим во множество число 0.

s.insert(0);

Совершаем k итераций.

for (i = 0; i < k; i++)

{

Извлекаем и удаляем наименьший элемент x.

x = *s.begin(); s.erase(x);

Для каждого i (1 ≤ i ≤ n) добавляем элементы x + a_i во множество;

for (j = 0; j < n; j++)

s.insert(x + m[j]);

}

Выводим ответ: k-ую наименьшую цену, которая равна наименьшему элементу множества.

printf("%lld\n", *s.begin());

Python реализация - TLE

Функция min() работает за O(n), так как она проходит по всем элементам множества, чтобы найти наименьший.

В Python множества являются неупорядоченными коллекциями, поэтому min() не может воспользоваться какой-либо заранее существующей упорядоченностью или структурой. Вместо этого она должна проверять каждый элемент по отдельности, чтобы определить минимум, что приводит к линейной временной сложности, пропорциональной количеству элементов в множестве.

n, k = map(int, input().split())

m = list(map(int, input().split()))

s = set({0})

for _ in range(k):

x = min(s)

s.remove(x)

for value in m:

s.add(x + value)

print(min(s))

Python реализация

SortedSet поддерживает элементы в отсортированном порядке, используя внутренний отсортированный список.

Доступ к элементу по индексу (например, s[0] для наименьшего элемента) выполняется за константное время, потому что SortedSet напрямую извлекает элемент по указанному индексу из своего внутреннего отсортированного списка без дополнительных вычислений.

Время выполнения операции add() в SortedSet из библиотеки sortedcontainers составляет O(log n), где n – количество элементов в множестве.

from sortedcontainers import SortedSet

n, k = map(int, input().split())

m = list(map(int, input().split()))

s = SortedSet([0])

for _ in range(k):

x = s[0]

s.discard(x)

for value in m:

s.add(x + value)

print(s[0])